package j2024.j202410;

public class j1022 {
    /**
     * 76. 最小覆盖子串
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
     * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     *
     *
     *
     * 注意：
     *
     * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        int kind = 0,begin = -1,minlen = Integer.MAX_VALUE;
        for(char ch:tt){
            if(hash1[ch]==0){
                kind++;
            }
            hash1[ch]++;
        }
        for (int left = 0,right = 0,count = 0; right < ss.length; right++) {
            //进
             char in = ss[right];
             hash2[in]++;
             if(hash2[in]==hash1[in]){
                 count++;
             }
             //出
             while(kind==count){
                 int len = right-left+1;
                 if(len<minlen){
                     minlen = len;
                     begin = left;
                 }
                 char out = ss[left++];
                 if(hash2[out]==hash1[out]){
                     count--;
                 }
                 hash2[out]--;
             }
        }
        if(begin==-1){
            return "";
        }
        return s.substring(begin,begin+minlen);
    }
}
